package com.feng.leetcode;

import jdk.nashorn.internal.runtime.StoredScript;

import java.util.regex.Pattern;

/**
 * @author feng
 * @decrition
 * @date 2022/3/2920:02
 */
public class L25 {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        listNode.next.next.next = new ListNode(4);
        ListNode listNode1 = reverseKGroup(listNode, 3);
        while (listNode1 != null) {
            System.out.println(listNode1.val);
            listNode1 = listNode1.next;
        }
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k < 2) {
            return head;
        }
        ListNode temp = head;
        for (int i = 0; i < k; i++) {
            if (temp == null) {
                return head;
            }
            temp = temp.next;
        }
        ListNode result = new ListNode();
        temp = result;
        while (temp != null) {
            ListNode one = head;
            ListNode stroe = new ListNode();
            ListNode stroeProxy = stroe;
            for (int i = 0; i < k; i++) {
                if (one == null) {
                    temp.next = head;
                    return result.next;
                } else {
                    stroeProxy.next = one;
                    stroeProxy = stroeProxy.next;
                }
                one = one.next;
            }
            head = one;
            int j = k;
            while (j > 0) {
                stroeProxy = stroe;
                for (int i = 0; i < j; i++) {
                    stroeProxy = stroeProxy.next;
                }
                temp.next = stroeProxy;
                temp = temp.next;
                temp.next = null;
                j--;
            }
        }
        return result.next;
    }

    private static void recursion(ListNode temp, ListNode head, int k) {
        if (k == 0) {
            temp.next = head;
            head = head.next;
            temp = temp.next;
            return;
        }
        recursion(temp, head, k);
        temp.next = head;
        head = head.next;
        temp = temp.next;

    }

    public static ListNode reverseKGroup1(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public static ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }

}
